import heapq
from typing import List


class Solution:
    def minTimeToReach(self, moveTime: List[List[int]]) -> int:
        inf = float('inf')
        queue = [((0,0), 0,1)]  # 某号节点,最早时间,第几次
        m = len(moveTime)
        n = len(moveTime[0])
        minTime = [[inf for _ in range(n)] for _ in range(m)]
        h = [1,2,1]
        while queue:
            (x,y), time,cnt = heapq.heappop(queue)
            if minTime[x][y] <= time: continue
            minTime[x][y] = time
            for nx, ny in [(x+1,y),(x-1,y),(x,y+1),(x,y-1)]:
                if nx < 0 or nx >= m: continue
                if ny < 0 or ny >= n: continue
                if minTime[nx][ny] <= time + cnt: continue

                heapq.heappush(queue, ((nx,ny),max(time, moveTime[nx][ny]) + cnt, h[cnt]))
        return minTime[-1][-1]


if __name__ == '__main__':
    s = Solution()
    r = s.minTimeToReach([[0,4],[4,4]])
    print(r)